The present invention relates generally to network packet routing and, specifically, to a method and apparatus for routing packets in a network in accordance with a longest prefix match of the destination address of the packet.
In many network systems, information transmitted through the network is organized in xe2x80x9cpackets.xe2x80x9d Each packet is transmitted by a sender node and routed from node to node in the network until it reaches a destination node specified in the packet. Each node that receives a packet must be able to decide which node should next receive that packet. This determination is generally done using a xe2x80x9cforwarding tablexe2x80x9d in the node. The node looks at the destination address of each individual packet and routes the packet to another node in accordance with the routing table and the packet""s destination address. This process is repeated in successive nodes until the packet reaches its destination.
In conventional networks, each node contains a forwarding table that maps an address prefix of a destination address in received packets to respective ports in the network. Routers, switches, ISs (Intermediate Systems), IMPs (Interface Message Processors), gateways and other similar elements also contain forwarding tables, and the term xe2x80x9crouterxe2x80x9d is used herein to refer to any node that routes or forwards received packets. If a received packet""s destination address has length W, the prefixes in the forwarding table may have lengths anywhere in the range 0 to W inclusive. For example, if a forwarding table contains routing information for prefixes of 1, 10, 100, 10010, and 111, a destination address of 10111 in a received packet has a longest prefix match of 10, since 10 is the longest prefix in the forwarding table that completely matches the destination address. When a packet arrives at a router, the router finds the longest prefix match in the router""s forwarding table and forwards the received packet accordingly. A longest matching prefix in the forwarding table needs to be found in a timely manner, since packets generally are routed in real-time and a router""s performance is based on how quickly it can forward a packet.
As an example, two conventional methods for performing address lookup in forwarding tables are binary search and TRIE (each of which is documented in Perlman, xe2x80x9cInterconnection: Bridges and Routers,xe2x80x9d pp 233-239, published by Addison Wesley 1992). Neither of these methods provide an ideal solution to the problem of finding a longest prefix match. Straightforward binary search, for example, does not work for address prefix lookups because the address prefixes can have different lengths. Therefore, a destination address may not match the prefixes in accordance with their alphabetized order. In the example above, if a forwarding table contains prefixes in alphabetized order of 1, 10, 100, 10010, and 111, an address of 10111 in a received packet will match the forwarding table prefix 10, even though it would be alphabetized after the prefix 10010. Because the forwarding table can have prefixes of varying lengths, finding a longest matching prefix in a forwarding table that matches a received destination address in as short a time as possible can be problematic. Similarly, while the TRIE method works correctly as a forwarding method, it lacks efficiency in routers where extremely high speeds are a requirement.
Various embodiments of the present invention can be implemented in hardware, software, or some combination of the two. In the described embodiments of the present invention, a node receives a packet that contains a destination address. The node then checks a router database to determine a longest prefix match for the destination address and further determines a port associated with the longest prefix match in the router database. The router database contains comparison values based on forwarding information specific to the router. A method in accordance with the present invention involves two parts: a first part looks at the routing information associated with a particular router and determines the data in the router database for that router. A second part searches the router database whenever a packet is received to determine a longest prefix match for a destination address in the received packet. The received packet is then routed to the port associated with the longest prefix match.
It is an important aspect of the present invention that a node routes a received packet in as little time as possible. Thus, while creation of the router database itself is not particularly time-critical, the actual process of searching the router database must be done very quickly. In the described embodiments of the present invention, a quick search is possible partly because of the way the router database is organized and partly because the search can involve parallel comparisons and/or parallel loads. In certain embodiments, the increase in speed is also due to specialized hardware/software used to search the router database.
Specifically, the described embodiments of the present invention allows lookup of a particular destination address prefix of size 0 through W to be performed in O(logk N), where N is the number of xe2x80x9cpadded prefixesxe2x80x9d in the router database. In the described embodiments, the routing information for each node includes several prefix/port pairs, which are used to determine the content of the router database for the node. In general, there are twice as many xe2x80x9cpadded prefixesxe2x80x9d in the router database as there are prefixes in the router""s forwarding information (there may sometimes be fewer than twice as many padded prefixes, as described below in detail in connection with various embodiments of the invention).
Specifically, the router database is organized into a comparison table having a number of xe2x80x9centries.xe2x80x9d Each xe2x80x9centryxe2x80x9d contains up to kxe2x88x921 values (or k values, in other embodiments). As used herein, xe2x80x9ckxe2x80x9d is the number of parallel elements required to compare the values in one entry in a router database to a received address (when the invention is implemented in hardware). Each of the values in a comparison table entry contains a xe2x80x9cpadded prefix.xe2x80x9d A corresponding table includes a pointer to a xe2x80x9cnext entryxe2x80x9d of data in the comparison table and may include additional information, such as port information. When a destination address in a packet is first received by a router, the values of a first one of the entries in the router database are loaded into the router to determine a port corresponding to the received destination address. As mentioned above, each entry in the comparison table has up to kxe2x88x921 (or k) values.
Certain embodiments of the invention allow the kxe2x88x921 (or k) values in a router database entry to be compared to the destination address in parallel. While the described embodiment can also be implemented on a general purpose computer, or on a computer having multiple processors, at least one embodiment of the present invention is implemented using hardware allowing very fast, parallel comparison of the values in a router database entry against the received destination address. For example, a described hardware implementation uses k comparisons. Another described hardware implementation uses kxe2x88x921 comparisons. A described software implementation uses kxe2x88x921 comparisons.
The comparison of the values in a first entry of the router database against the destination address identifies a next entry in the comparison database, which is, in turn, loaded and compared to the destination address. This process of loading a xe2x80x9cnext entryxe2x80x9d from the comparison table and performing fast k-ary compares against the destination address is repeated until there are no more xe2x80x9cnext entriesxe2x80x9d in the database. At this point, a longest prefix match has been found and the packet is routed to a port associated with the longest prefix match in the router database.
In at least one described embodiment, creation of the router database proceed as follows. (Each router has associated routing information comprising 2 pairs.) First, the prefixes are padded with ones and with zeroes to a length of the maximum address length +1. Next a mask is associated with each zero-padded prefix and an all-zero padded 2 pair is added if one does not already exist. The padded 2 pairs are then sorted and a xe2x80x9csmaller maskxe2x80x9d is determined for each one-padded prefix. The smaller mask allows the described embodiments of the present invention to find closest matches, as described below in detail. Next, duplicate padded 2 pairs are removed, leaving xe2x80x9cNxe2x80x9d padded prefix router pairs. Finally, the sorted padded 2 pairs are distributed into xe2x80x9centriesxe2x80x9d having up to kxe2x88x921 (or k) padded 2 pairs in each entry.
In accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to a method of finding a longest match for a piece of target data against a group of comparison values, comprising the steps, performed by a data processing system of accessing at least one of a plurality of entries in a comparison data structure, each entry in the data structure having at most kxe2x88x921 comparison values and k addresses of a next data structure entry, where 2 less than =k less than =N, and where N is the total number of comparison values; and comparing kxe2x88x921 comparison values in the at least one of the data structure entries to the target data, in parallel, to determine a longest matching value.
In further accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to an apparatus that finds a longest match for a piece of target data against a group of comparison values, comprising: a portion configured to access at least one of a plurality of entries in a comparison data structure, each entry in the data structure having at most kxe2x88x921 comparison values and k addresses of a next data structure entry, where 2 less than =k less than =N, and where N is the total number of comparison values; and a portion configured to compare kxe2x88x921 comparison values in the at least one of the data structure entries to the target data, in parallel, to determine a longest matching value.
In further accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to a method of finding a longest match for a piece of target data against a group of comparison values, comprising the steps, performed by a data processing system of: accessing at least one of a plurality of entries in a comparison data structure, each entry in the data structure having at most k comparison values and k addresses of a next data structure entry, where 2 less than =k less than =N, and where N is the total number of comparison values; and comparing k comparison values in the at least one of the data structure entries to the target data, in parallel, to determine a longest matching value.
In further accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to an apparatus that finds a longest match for a piece of target data against a group of comparison values, comprising: a portion configured to access at least one of a plurality of entries in a comparison data structure, each entry in the data structure having at most k comparison values and k addresses of a next data structure entry, where 2 less than =k less than =N, and where N is the total number of comparison values; and a portion configured to compare k comparison values in the at least one of the data structure entries to the target data, in parallel, to determine a longest matching value.
In further accordance with the purpose of the invention, as embodied and broadly described herein, the invention relates to a method of determining contents of a router database used to find a longest matching prefix for an address in a packet received by a router, comprising the steps of: creating a one-padded prefix and a zero-padded prefix for each of a plurality of prefixes for which the router has an associated port; associating a mask with each zero-padded prefix; sorting the padded prefixes, keeping each padded prefix paired with its associated mask; for each one-padded prefix, changing its mask to a xe2x80x9csmallerxe2x80x9d mask by performing a loop through the padded prefixes having a lower sorted order than the one-padded prefix; and removing all duplicate padded prefixes, leaving a padded prefix with a highest sorted order mask if the prefix is zero-padded; and leaving a padded prefix with a lowest sorted order mask if the prefix is one-padded.
Advantages of the invention will be set forth in part in the description which follows and in part will be obvious from the description or may be learned by practice of the invention. The objects and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims and equivalents.